/*
 * 11.3
 * Given an input file with four billion integers, provide an algorithm to generate an
 * integer which is not contained in the file. Assume you have 1 GB of memory.
 * FOLLOW UP
 * What if you have only 10 MB of memory?
 */
#include <stdio.h>

const int max = 100 * 1000 * 1000; // 100M, and assuming memory limit is 1M.
int data[max];

/*
 * - It’s possible to find a missing integer with just two passes of the data set. We can divide up
 * the integers into blocks of some size (we’ll discuss how to decide on a size later). Let’s just as-
 * sume that we divide up the integers into blocks of 1000. So, block 0 represents the numbers
 * 0 through 999, block 1 represents blocks 1000 - 1999, etc. Since the range of ints is finite, we
 * know that the number of blocks needed is finite.
 * - In the first pass, we count how many ints are in each block. That is, if we see 552, we know
 * that that is in block 0, we increment counter[0]. If we see 1425, we know that that is in block
 * 1, so we increment counter[1].
 * - At the end of the first pass, we’ll be able to quickly spot a block that is missing a number. If
 * our block size is 1000, then any block which has fewer than 1000 numbers must be missing a
 * number. Pick any one of those blocks.
 * - In the second pass, we’ll actually look for which number is missing. We can do this by creat-
 * ing a simple bit vector of size 1000. We iterate through the file, and for each number that
 * should be in our block, we set the appropriate bit in the bit vector. By the end, we’ll know
 * which number (or numbers) is missing.
 */

/*
 * - max = 2^27, limit = 2^20.
 * let blocks = 2^x
 *   --> counter memory = 2^x * 4 = 2^(x+2) <= 2^20
 *   --> single block memory = (2^27 / 2^x) / 2^3 <= 2^20
 *     --> 4 <= x <= 18
 */
int search()
{
    const int block_size = 1000;
    const int blocks = max / block_size + 1;
    int *counter_array = new int[blocks](); /* XXX: no arguments allowed */
    int i;
    for (i = 0; i < max; ++i) {
        counter_array[data[i]/block_size]++;
    }
    i = 0;
    for ( ; i < blocks; ++i) {
        if (counter_array[i] < block_size) {
            break;
        }
    }
    delete[] counter_array;
    if (i == blocks) {
        return -1;
    }
    /* find in a single block */
    int size = block_size / 8 + 1;
    char *block_array = new char[size](); /* XXX: no arguments allowed */
    int j;
    for (j = 0; j < max; ++j) {
        if (data[j]/block_size == i) {
            int idx = data[j] % block_size;
            block_array[idx/8] |= 1 << (idx%8);
        }
    }
    j = 0;
    for ( ; j < block_size; ++j) {
        if ((block_array[j/8] & (1 << (j%8))) == 0) { /* XXX: "==" has higher priority than "&" */
            break;
        }
    }
    delete[] block_array;
    if (j == block_size) {
        return -1;
    }
    return i*block_size+j;
}

int main()
{
    for (int i = 0; i < max; ++i) {
        data[i] = max - i - 1;
    }
    data[1024] = 65536;
    int k = search();
    printf("find k = %d\n", k);
    return 0;
}
